1. Field of the Invention
The present invention relates to a method for filling a polygon to be displayed in computer graphics based on the information stored in a display memory.
2. Description of the Background Art
Filling of a polygon in computer graphics has been implemented by using a scan line method and the like in the background art. This is a method in which a polygon is scanned from top to bottom with a horizontal line called a scan line to draw according to the following steps:
1. Take the scan line at the top of a polygon,
2. Repeat the following steps until the scan line reaches the bottom;
2-1. Obtain sides which intersect the scan line, PA1 2-2. Obtain points of intersection of the scan line and these sides, PA1 2-3. Sort the points of intersection according to x-coordinate, PA1 2-4. Make pairs of two points of intersection in ascending order of x-coordinate and fill the two through, PA1 2-5. Move to a lower scan line by one,
3. End.
In the step 2-2 of obtaining points of intersection of the scan line and these sides, when a point of intersection is a vertex of a polygon and the vectors of two sides have upward and downward directions, an exceptional process is performed, assuming that there are two points of intersection at the vertex. With respect to an object of FIG. 59, the exceptional process is performed on the points at the coordinates (S1, H4), (S2, H11), (S5, H8), (S6, H7), (S8, H5) and (S10, H11).
For example, when the line segments in the object of FIG. 59 are selected in a counterclockwise rotation as shown in FIG. 60, as the line-segment vector A1 (H4-H8, S1-S5) is in an upward direction (which makes an upward vertical-coordinate variation) and the line-segment vector A2 (H1-H4, S4-S1) is in a downward direction (which makes a downward vertical-coordinate variation), it is assumed that there are two points of intersection at the coordinate (H4, S1) having two sides of the vectors A1 and A2.
On the other hand, another method for filling a polygon is an outline font method, using a drawing work memory of 1 bit/pixel. This is a method in which the bits for the line segments of a polygon and in their right directions are inverted in a work memory (1 bit/pixel) having a minimum rectangular which surrounds an area to be drawn to make a drawing in the area of 1 bit/pixel and the drawing information in the work memory is transferred with extension to a display memory to draw a filled polygon thereon.
In the outline font method, based on outline information defining line segments constituting the outline of a polygon to be filled, selecting a line segment in a predetermined rotation, all the bits for the selected line segment and in its right direction on horizontal coordinate on the work memory are inverted to draw a filled object on the work memory. This process is performed according to the following conditions A) to G):
A) When both a line segment to be now subjected to the bit inversion and a line segment to be next have upward vectors (which makes an upward vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
B) When both a line segment to be now subjected to the bit inversion and a line segment to be next have downward vectors (which makes a downward vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
C) When a line segment to be now subjected to the bit inversion has an upward vector and a line segment to be next has a downward vector, the bits in the right direction of the line segment inclusive of the initial point and the terminal point are inverted.
D) When a line segment to be now subjected to the bit inversion has a downward vector and a line segment to be next has an upward vector, the bits in the right direction of the line segment inclusive of the initial point and the terminal point are inverted.
E) When a line segment to be now subjected to the bit inversion has a downward vector and a line segment to be next has a horizontal vector (which makes no vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
F) When a line segment to be now subjected to the bit inversion has an upward vector and a line segment to be next has a horizontal vector (which makes no vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
G) When a line segment to be now subjected to the bit inversion has a horizontal vector and a line segment to be next has a downward vector, the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
H) When a line segment to be now subjected to the bit inversion has a horizontal vector and a line segment to be next has an upward vector, the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
The outline font method will be discussed below, taking a triangle to be filled having the outline shown in FIG. 61 as an example. First, the coordinates of three vertices {P1(H8, S2), P2(H2, S15), P3(H16, S11)} are obtained as the outline information.
With respect to a triangle to be filled, the line-segment vectors L1 (H2-H8, S15-S2), L2 (H16-H2, S11-S15) and L3 (H8-H16, S2-S11) are selected in this order in a counterclockwise rotation as shown in FIG. 62. A plane work area on the work memory is blank (nothing is drawn) in an initial state.
First, the line segment L1 is obtained from the coordinates of the vertices P1 and P2 given as the outline information, using an already-existing linear algorithm such as Bresenham algorithm, as shown in FIGS. 63 and 64, and all the bits in the right direction of the line segment L1 on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted for drawing.
FIG. 63 shows a halfway state of the bit inversion of the line segment L1 and FIG. 64 shows the final result of the bit inversion. As the line segment L1 is in the downward direction and the line segment L2 is in the upward direction, according to the condition D), the bits in the right direction of the line segment L1 inclusive of the initial point and the terminal point are inverted.
Secondly, the line segment L2 is obtained from the coordinates of the vertices P2 and P3 given as the outline information, using the already-existing linear algorithm such as Bresenham algorithm, as shown in FIG. 65 and all the bits in the right direction of the line segment L2 on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted. As a result, some of the already-drawn bits of FIG. 64 are inverted again to be back in blank.
FIG. 65 shows a halfway state of the bit inversion of the line segment L2. As the line segments L2 and L3 are both in the upward direction, according to the condition A), the bits in the right direction of the line segment L2 inclusive of the initial point and not inclusive of the terminal point are inverted.
Similarly, the line segment L3 is obtained from the outline information, and all the bits in the right direction of the line segment L3 on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted, to complete the triangle which is filled inside as shown in FIG. 66. As the line segment L3 is in the upward direction and the line segment L1 is in the downward direction, according to the condition C), the bits in the right direction of the line segment L3 inclusive of the initial point and the terminal point are inverted.
After that, the drawing information on the plane work area of the work memory is transferred with extension to a plane display area of the display memory and the triangle which is filled inside is displayed, based on the information stored in the display memory. "Extension" refers to addition of another information such as color information.
Furthermore, in the above outline font method, though the bits in the right direction of each line segment of a polygon are inverted, it is possible, on the same principle, that the bits in the left direction of each line segment of the polygon are inverted.
When it is intended that a large object is drawn through this method, the object is divided into parts so that each of the parts can be processed on the plane work area of the work memory. The divided parts are filled on the respective plane work areas of the work memory and then sequentially transferred to the display memory. That allows filling of a large object even with a work memory having small plane work areas.
The background-art computer graphics adopts the scan line method or the outline font method as discussed above.
The scan line method needs a sort of points of intersection at every raster (scan line) and a relatively large memory to store information on line segments (initial point, terminal point, slope and the like).
As the number of vertices increases, the number of memories increases since memories as much as vertices are needed and also the load on the processor increases with an increase in the number of points of intersection to be sorted.
On the other hand, the outline font method is not likely to have the above disadvantage but has another problem of inaccuracy of filling due to 1-bit (1 -pixel) lack on the right side (lack on the left side in a case of the bit inversion in the left direction) of the drawn polygon in drawing a polygon on the 1-bit/pixel plane work area of the work memory according to the conditions A) to H).